A parallel computer network often encompasses communication among a number of nodes. One example of a parallel computer network is a multiple instruction streams, multiple data streams ("MIMD") computer. Each node usually has a processor coupled to a memory. Typically, the nodes operate independently and interact with each other by sending and receiving messages or blocks of data.
Practicability dictates every node cannot have a dedicated link to the thousands of other nodes in a large parallel computer network or system. Rather, the system usually interconnects the nodes in a regular topology or structure, such as a ring, tree, or multi-dimensional mesh or torus. Generally, each node has a direct link to only a few of its neighboring nodes. Data communication between nodes without direct links utilizes intermediate nodes.
A node that originates a message can address the message to a single recipient or to multiple recipients. Namely, an individual-addressee message has a single intended recipient. Further, when the originating node intends to send particular data to a number of other nodes, the originator can send a broadcast message, rather than send separate individual-addressee messages to each of the nodes. Moreover, a broadcast message can be selective (so it has specific, multiple intended recipients) or be network-wide.
In one known individual-addressee communication design, a routing mechanism associated with each node interfaces that node with the computer network. Furthermore, a routing mechanism (associated with an intermediate node) both receives data from a preceding routing mechanism and also transmits the data to another routing mechanism in a byte-by-byte fashion. Moreover, an intermediate routing mechanism relays an acknowledgement from a subsequent routing mechanism to a preceding routing mechanism without taking any action. Such a design is disclosed in U.S. Pat. No. 5,181,017 to Frey, Jr. et al. (entitled "Adaptive Routing in a Parallel Computing System," issued Jan. 19, 1993, and assigned to International Business Machines Corporation), which is hereby incorporated herein by reference in its entirety. A shortcoming of this design, however, is the inability of any routing mechanism to transmit a portion of, for instance, a broadcast message to another node before storing the entire message in memory of a local node. A further shortcoming is the inability of an intermediate routing mechanism to take any action concerning acknowledgement of a message, for instance, during broadcasting.
During one common type of broadcasting, the originator serially sends its broadcast message to its linked set of nodes. Next, after receiving the entire message, each node of the set runs software to process and store the broadcast data. Then, each of these nodes serially sends out to its linked nodes in the network a new message containing the broadcast data. Eventually, all the nodes contain a copy of the serially processed-stored-forwarded data. A shortcoming of this arrangement is the inability of an intermediate node to transmit any of the data to another node before receipt of the entire message. A further shortcoming is the inability of the intermediate node to communicate received data without generating a new message. Another shortcoming is the inability of the intermediate node to store any portion of the data in its local node memory and transmit the portion to another node on a portion-by-portion basis.
In another known configuration, a routing mechanism (in a network in which nodes and routing mechanisms are associated one-for-one) collects subsequent intended recipient acknowledgement information for an individual-addressee node message and returns the status to a preceding routing mechanism (toward the originator). Such a design is disclosed in U.S. Pat. No. 5,404,565 to Gould et al. (entitled "Message Tracking in a Parallel Network Employing a Status Word at Each Node Which Reflects a Message's Progress," issued Apr. 4, 1995, and assigned to International Business Machines Corporation), which is hereby incorporated herein by reference in its entirety. A shortcoming of this configuration is the inability of the routing mechanism to return to a preceding routing mechanism a status of whether a broadcast message has been received by its local associated node in addition to a number of other nodes. Another shortcoming is the inability of an intermediate routing mechanism to transmit any of the data to another routing mechanism before receipt of the entire message. An additional shortcoming is the inability of any routing mechanism to substantially simultaneously store in its local node and transmit to another routing mechanism a received portion of a broadcast message.
Thus, a need exists for a capability that provides storing of data of a message in memory of a local node and transmitting of the data toward another node before receipt of the entire message. An additional need exists for a technique that allows transmission of received broadcast data toward another node without generating a new message. A further need exists for a capability that provides transmission of a portion of a broadcast message to another node before storing the entire message in memory of a local node. Another need exists for a technique that allows intermediate routing mechanism action concerning acknowledgement of a broadcast message. A still further need exists for a capability that provides return by one routing mechanism to its preceding routing mechanism of a status whether a broadcast message has been received by its local associated node in addition to a number of other nodes.